package 递归回溯;

import com.alibaba.fastjson.JSON;
import common.GeneralFunction;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class No22括号生成 {

    /**
     * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
     *
     * 示例 1：
     * 输入：n = 3
     * 输出：["((()))","(()())","(())()","()(())","()()()"]
     * 示例 2：
     * 输入：n = 1
     * 输出：["()"]
     *  
     * 提示：
     * 1 <= n <= 8
     */

    private List<String> list=new ArrayList<>();
    private int length=0;

    //我的题题解写的过于复杂(想错了一步,但缝补一下,结果还是对的),下面有参考题目之后写的已经清晰的
    public List<String> generateParenthesis(int n) {
        dg(n,n,new ArrayDeque<>());
        list.add("---");
        this.length=n;
        dfs(n,n,new ArrayDeque<>());
        return list;
    }

    private void dg(int leftCount, int rightCount, Deque<String> path){

        if(rightCount==0){
            StringBuilder stringBuilder=new StringBuilder();
            for (String s : path) {
                stringBuilder.append(s);
            }
            list.add(stringBuilder.toString());
            return;
        }

        if(leftCount==0){
            path.add(")");
            dg(leftCount,rightCount-1,path);
            path.removeLast();
            return;
        }

        if(leftCount==rightCount){
            path.addLast("(");
            dg(leftCount-1,rightCount,path);
            path.removeLast();
        }else if(leftCount>rightCount&& path.peek().equals(")")){
            path.addLast(")");
            dg(leftCount,rightCount-1,path);
            path.removeLast();
        }else{
            path.addLast("(");
            dg(leftCount-1,rightCount,path);
            path.removeLast();

            path.addLast(")");
            dg(leftCount,rightCount-1,path);
            path.removeLast();
        }

    }

    private void dfs(int openCount,int closeCount,Deque<String> path){

        if(path.size()==length*2){
            StringBuilder stringBuilder=new StringBuilder();
            for (String s : path) {
                stringBuilder.append(s);
            }
            list.add(stringBuilder.toString());
            return;
        }

        if(openCount>0){
            path.add("(");
            dfs(openCount-1,closeCount,path);
            path.removeLast();
        }
        if(closeCount>openCount){
            path.add(")");
            dfs(openCount,closeCount-1,path);
            path.removeLast();
        }

    }

    public static void main(String[] args) {
        GeneralFunction generalFunction=new GeneralFunction(No22括号生成.class,3);
        generalFunction.runAllMethod();

    }

}
